package chapter6;

import java.util.LinkedList;
import java.util.Queue;

//LC 279

/**
 * 广度优先
 */
public class PerfectSquares {
    class Pair {
        int num;
        int step;
        Pair(int num, int step) {
            this.num = num;
            this.step = step;
        }
    }

    public int numSquares(int n) {
        Queue<Pair> q = new LinkedList<>();
        int[] visited = new int[n+1];
        q.add(new Pair(n, 0));
        while (!q.isEmpty()) {
            Pair pair = q.poll();
            int num = pair.num;
            int step = pair.step;
            if (num == 0) {
                return step;
            }
            for (int i = 1; ; i++) {
                int next = num - i * i;
                if (next < 0) break;
                if (next == 0) return step + 1;
                if (visited[next] == 0) {
                    q.add(new Pair(next , step +1 ));
                    visited[next] = 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new PerfectSquares().numSquares(13));
    }
}
